#include <stdio.h>
#include <string>
#include <list>
#include <iostream>

using namespace std;

class tree{
	public:
		tree(string n){
			name = n;
		}
		~tree(){

		}
		string getName(){
			return name;
		}
		void setBranch(tree* b1, tree* b2){
			branch1 = b1;
			branch2 = b2;
			return;
		}

		tree* branch1;
		tree* branch2;
		string name;
};

tree* buildTree(){

	tree* t0 = new tree("GrandPa");
	tree* t1 = new tree("John");
	tree* t2 = new tree("Vannessa");

	tree* t3 = new tree("Jim");
	tree* t4 = new tree("Jackie");

	tree* t5 = new tree("Chieh");
	tree* t6 = new tree("Kathia");

	t0->setBranch(t1, t2);
	t1->setBranch(t3, t4);
	t2->setBranch(t5, t6);

	t3->setBranch(0, 0);
	t4->setBranch(0, 0);
	t5->setBranch(0, 0);
	t6->setBranch(0, 0);

	return t0;
}


string findName_bfs2(list<tree*> &tl, string curName, string searchName){

	list<tree*> tl2;

	while(tl.size() != 0){
		tree* node = *tl.begin();
		cout << curName << "   " << node->getName() << endl;
	
		if(node->name == searchName){
			return curName + " -> " + node->name;
		}else{
			if(node->branch1 != 0) tl2.push_back(node->branch1);	
			if(node->branch2 != 0) tl2.push_back(node->branch2);	
		}
		tl.pop_front();	
	}
	printf("\n--------------\n");

	if(tl2.size() !=0){
		string v = findName_bfs2(tl2, "layer" , searchName);
	}

	return "None";
}



string findName_bfs(list<tree*> &tl, string curName, string searchName){

	while(tl.size() != 0){
		tree* node = *tl.begin();
		cout << node->getName() << endl;
	
		if(node->name == searchName){
			return curName + " -> " + node->name;
		}else{
			if(node->branch1 != 0) tl.push_back(node->branch1);	
			if(node->branch2 != 0) tl.push_back(node->branch2);	
		}
	
		tl.pop_front();	
	}
	return "None";
}

string findName_dfs(tree* t, string curName, string searchName){
	if(t->getName() == searchName){
		return curName + " -> " + t->getName();
	}else{
		if(t->branch1 == 0){
			return "Bottom";
		}

		string branch1_res = findName_dfs(t->branch1, t->getName(), searchName);
		string branch2_res = findName_dfs(t->branch2, t->getName(), searchName);

		if(branch1_res != "Bottom" ){
			return curName + " -> " + branch1_res;
		}
		else if(branch2_res != "Bottom" ){
			return curName + " -> " + branch2_res;
		}
		return "Bottom";
	}
}

int main(){
	tree* grandpa = buildTree();
	list<tree*> listTree;
	listTree.push_back(grandpa);

	findName_bfs(listTree, "", "Chieh");
	printf("\n============\n");
	findName_bfs2(listTree, "", "Chieh");
	printf("\n============\n");
	string path = findName_dfs(grandpa, "", "Chieh");
	printf("%s\n", path.c_str());
	return 0;
}
